#include <iostream>
using namespace std;

struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode() : val(0), left(nullptr), right(nullptr) {}
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
	TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};


class Solution{
private:
	int getDepth(TreeNode* node){
		if(node == nullptr){
			return 0;
		}
		int leftDepth = getDepth(node->left);
		int rightDepth = getDepth(node->right);
		if(node->left != nullptr && node->right == nullptr){
			return 1 +leftDepth;
		}
		if(node->right != nullptr && node->left == nullptr){
			return 1 +rightDepth;
		}
		return 1 + min(leftDepth,rightDepth);
	}
public:
	int minDepth(TreeNode* root){
		return getDepth(root);
	}
};

class Solution2{
private:
	int result;
	void getDepth(TreeNode* node,int depth){
		if(node == nullptr){
			return;
		}
		// 中
		if(node->left == nullptr && node->right == nullptr){
			result = depth < result ? depth : result;
		}
		// 左边
		getDepth(node->left,depth+1);
		getDepth(node->right,depth+1);
	}
public:
	int minDepth(TreeNode* root){
		if(root == nullptr){
			return 0;
		}
		result = INT_MAX;
		getDepth(root,1);
		return result;
	}
};
